package com.leetcode.contest;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/11/4 10:01
 */
public class LC2059转化数字的最小运算数 {

    public static int minimumOperations(int[] nums, int start, int goal) {
        //图，最短路径，优先队列控制最小转换次数  [curNum, steps]
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        boolean[] visited = new boolean[1001];
        visited[start] = true;
        minHeap.offer(new int[]{start, 0});
        while (!minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            int curValue = cur[0], steps = cur[1];
            //控制数据需要在规定范围内
            if (curValue > 1000 || curValue < 0) continue;
            if (curValue == goal) return steps;
            for (int num : nums) {
                int num1 = curValue + num, num2 = curValue - num, num3 = curValue ^ num;
                //如果直接计算能够到达goal节点，直接返回steps+1
                if (num1 == goal || num2 == goal || num3 == goal) return steps + 1;
                //要求下一步的节点在范围内，且没有被访问，避免形成回路导致死循环
                if ((num1 >= 0 && num1 <= 1000) && !visited[num1]) {
                    minHeap.offer(new int[]{num1, steps + 1});
                    visited[num1] = true;
                }
                if ((num2 >= 0 && num2 <= 1000) && !visited[num2]) {
                    minHeap.offer(new int[]{num2, steps + 1});
                    visited[num2] = true;
                }
                if ((num3 >= 0 && num3 <= 1000) && !visited[num3]) {
                    minHeap.offer(new int[]{num3, steps + 1});
                    visited[num3] = true;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {2, 8, 16};
        System.out.println(minimumOperations(nums, 0, 1));
    }
}
